/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2022-08-13
 * Time: 17:48
 */
public class MyLinkedList {
        public class Node{
            int val;
            Node next;

            public Node(int val) {
                this.val = val;
            }
        }
        Node head;
        //打印链表
        public void dispaly(){
            Node cur = this.head;
            while (cur != null){
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
        }
        //头插法
        public void add(int data){
            Node node = new Node(data);
            //空表
            if(head == null){
                head =node;
            }else{
                node.next = head;
                head = node;
            }

        }
        //尾插法
        public void lastAdd(int data){
            Node node = new Node(data);
            //空表
            if(head == null){
                head = node;
            }else{
                //非空表
                Node cur = this.head;
                while(cur.next != null){
                    cur = cur.next;
                }
                //cur.next == null 尾结点处
                cur.next = node;

            }


        }
        //获取链表的长度
        public int size(){
            Node cur = this.head;
            int count  = 0;
            while (cur != null){
                count++;
                cur = cur.next;
            }
            return count;
        }
        //任意位置index插入法
        public void indexAdd(int index,int data){
            Node node = new Node(data);
            //如果为空表
            if(head == null){
                head = node;
            }else{//不为空表
                //检查index的位置是否合法
                checkIndex(index);
                //头插
                if(index == 0){
                    add(data);
                }else if(index == size()){//尾插
                    lastAdd(data);
                }else{//中间位置 且index位置合法
                    //找index的位置前驱
                    Node cur = findSubOne(index);
                    node.next = cur.next;
                    cur.next = node;
                }
            }

        }
        //找index的前驱
        private Node findSubOne(int index){
            Node cur = head;
            while (index - 1 != 0){
                cur=cur.next;
                index--;
            }
            return cur;
        }
        //检查index的位置是否合法
        private void checkIndex(int index){
            if(index <0 || index > size()){
                throw new IndexILLlegal("index位置异常");
            }
        }










    public Node reverseBetween ( int m, int n) {

        // write code here
        Node left = head;//左区间
        Node right = head;//右区间
        Node inforLeft = head;//左区间的前驱
        int tmp = m;

        int len = n-m;//区间长度

        while(m-1!=0){//找到左区间
            left=left.next;
            m--;
        }

        while(tmp-2!=0){//找到左区间的前驱
            inforLeft = inforLeft.next;
            tmp--;
        }
        while(n-1!=0){//找右区间
            right = right.next;
            n--;
        }
        Node nextRight = left;
        while(len != 0){//反转次数
            Node nextInforLeft = inforLeft.next;
            inforLeft.next = right;
            right.next = nextInforLeft;
            len--;
            nextInforLeft = right;
            while(len != 0){
                nextRight=nextRight.next;
                len--;
            }
            right = nextRight;

        }
        return head;


    }


    }

